***************************************************************************************************************************
									50.递归的定义和不同函数之间相互调程序举例	2012.3.29
									51.一个函数自己调自己程序举例				2012.3.29
									52.1+2+3+....+100之和用递归来实现			2012.3.29
									53.布置作业_汉诺塔							2012.3.29
									54.一个函数为什么可以自己调用自己			
									55.递归必须满足3个条件						2012.3.29
									56.递归和循环的比较							2012.3.29
									57.汉诺塔问题								2012.3.29
									58.递归的应用								2012.3.29
***************************************************************************************************************************
专题：递归（靠栈来实现）
	定义：函数自己调用自己（直接或间接）
	1.1+2+3+4+...+100
	2.求阶乘
	3.汉诺塔
	4.走迷宫
//************************
//----函数自己调自己----
#include 	"stdio.h"

void f(int n)
{
	if(n==1)
	printf("哈哈\n");
	else
	f(n-1);
}

void main()
{
	void f(3);
	return;
}
//***********************************

//***********************************
//------求阶乘 非递归法---
void main()
{
	int val,mult=1,i=1;
	printf("请输入需要求阶乘的值：");
	scanf("%d",&val);
	
	for (;i<val+1;i++)
	{
		mult=mult*i;
	}
	printf("%d的阶乘是%d\n",val,mult);
}
//***********************************	
							
							
//***********************************
//------求阶乘 递归法-------
#include "stdio.h"

long factorial(long n)
{
	if (1==n)
	{
		return 1;
	} 
	else
	{
		return factorial(n-1)*n;
	}
}

void main()
{
	printf("%d\n",factorial(5));
}												
//***********************************

//***********************************
//------求1+2+3...+100 递归法-------
#include "stdio.h"

long sum(int n)
{
	int i,j,k;
	if(1==n)
	{
		return 1;
	}
	else
	{
		return (sum(n-1)+n);
	}
}

void main()
{
	printf("%d\n",sum(100));
}
//***********************************

//*************************************************
//-----------------汉诺塔--------------------							
#include "stdio.h"

int move_count=0;

void	hanoi(int n,char x,char y,char z)
{
	void move(char a,char b,int n);
	if (1==n)
	{
		move(x,z,n);
//		return 1;
	}
	else
	{
		hanoi(n-1,x,z,y);
		move(x,z,n);
		hanoi(n-1,y,x,z);

	}
}

void	move(char a,char b,int n)
{
	if (1!=n)
	{
		move_count+=1;
	}
	printf("%c-->%c\n",a,b);
}	

void	main()
{
	int n;
	printf("请输入碟子数目：");
	scanf("%d",&n);
	hanoi(n,'A','B','C');
	printf("共需要%d个步骤!\n",move_count*2+1);
}
//*************************************************
							
递归必须满足的3个条件：
					1.必须有一个明确的终止条件；
					2.该函数所处理的数据规模必须递减；
					3.这个转化必须是可解的（郝斌自己加的）
							
递归和循环的优缺点：
				递归：
					易于理解
					速度慢
					存储空间大
						  
				循环：
					不易理解
					速度快
					存储空间小
							
							
递归的应用：
			1.树和森林是以递归定义的;
			2.树和图的很多算法是以递归实现的；
			3.很多数学公式就是以递归的方式定义的
							